package com.major.dawn.leetCode.string;


import java.util.*;

public class PermutationString {

    //    穷举
    public String[] permutation(String s) {
        if (s == null || s.equals("")) {
            return new String[0];
        }
        Set<String> stringSet = new HashSet<>();
        char[] toChars = s.toCharArray();
        ArrayList<Character> characters = convertToList(toChars);

        fillChars(toChars, characters, 0, stringSet);

        return stringSet.toArray(new String[stringSet.size()]);
    }

    private ArrayList<Character> convertToList(char[] toChars) {
        ArrayList<Character> charactersList = new ArrayList<>();
        for (int i = 0; i < toChars.length; i++) {
            charactersList.add(toChars[i]);
        }
        return charactersList;
    }

    private void fillChars(char[] chars, ArrayList<Character> characters, int seat, Set<String> stringSet) {

        int size = characters.size();
        if (size > 1) {
            for (int i = 0; i < size; i++) {
                chars[seat] = characters.get(i);
                int next = seat + 1;
                ArrayList<Character> charactersList = new ArrayList<>();
                charactersList.addAll(characters);
                charactersList.remove(i);
                fillChars(chars, charactersList, next, stringSet);

            }
        }

        if (size == 1) {
            chars[seat] = characters.get(0);
            String valueOf = String.copyValueOf(chars);
            stringSet.add(valueOf);
        }

    }


    //    回溯法  和穷举的思路大致是相同的，主要比较交换，和减枝的思路
    public String[] permutationDfs(String s) {
        if (s == null || s.equals("")) {
            return new String[0];
        }

        char[] chars = s.toCharArray();
        List<String> stringList = new ArrayList<>();
        fillStringLing(stringList, chars, 0);
        return stringList.toArray(new String[stringList.size()]);
    }

    private void fillStringLing(List<String> stringList, char[] chars, int seat) {
        int length = chars.length;
        int loop = length - seat;

        char[] copyChars = chars.clone();

        HashSet<Character> characterHashSet = new HashSet<>();

        if (loop > 1) {
            for (int i = seat; i < length; i++) {
                char aChar = chars[i];
                if (!characterHashSet.contains(aChar)) {
                    characterHashSet.add(aChar);
                    swapSeat(seat, i, copyChars);
                    int nextSeat = seat + 1;
                    fillStringLing(stringList, copyChars, nextSeat);
                    swapSeat(i, seat, copyChars);
                }

            }
        }

        if (loop == 1) {
            String valueOf = String.copyValueOf(copyChars);
            stringList.add(valueOf);
        }

    }

    private char[] swapSeat(int seat, int i, char[] chars) {
        char aChar = chars[seat];
        char iChar = chars[i];
        chars[seat] = iChar;
        chars[i] = aChar;
        return chars;
    }


    //    字典序
    public String[] permutationDic(String s) {
        if (s == null || s.equals("")) {
            return new String[0];
        }
        char[] chars = s.toCharArray();
//    排序
        insertSort(chars);
        ArrayList<String> stringArrayList = new ArrayList<>();

        stringArrayList.add(String.copyValueOf(chars));

        int length = chars.length;

        int loop = length - 2;

        for (int i = loop; i >= 0; i--) {

            for (int j = length-1; j > loop; j--) {
                if (chars[i] < chars[j]) {
                    swap(chars, j, i);
                    stringArrayList.add(String.copyValueOf(chars));
                }
            }
        }
        return stringArrayList.toArray(new String[stringArrayList.size()]);
    }


    public static void insertSort(char[] chars) {

        int length = chars.length;

        for (int i = 1; i < length; i++) {

            for (int j = 0; j < i; j++) {
                if (chars[i] < chars[j]) {
                    swap(chars, i, j);
                    break;
                }
            }
        }
    }

    public static void swap(char[] chars, int insertSeat, int curSeat) {
        char aChar = chars[insertSeat];

        System.arraycopy(chars, curSeat, chars, curSeat + 1, insertSeat - curSeat);
        chars[curSeat] = aChar;
    }


    public static void main(String[] args) {
        PermutationString permutationString = new PermutationString();
        String[] abcs = permutationString.permutation("abc");
        for (int i = 0; i < abcs.length; i++) {
            System.out.print(abcs[i] + ",");
        }

        System.out.println("---------------------");

        String[] permutationDfs = permutationString.permutationDfs("abc");
        for (int i = 0; i < permutationDfs.length; i++) {
            System.out.print(permutationDfs[i] + ",");
        }
        System.out.println("---------------------");

        String[] permutationDic = permutationString.permutationDic("abc");
        for (int i = 0; i < permutationDic.length; i++) {
            System.out.print(permutationDic[i] + ",");
        }
    }
}
